package com.lijing.fibonacciSearch;

import java.util.Arrays;

public class FibonacciSearch {
    public static void main(String[] args) {
        int[] arr = {1,8,10,89,1000,1234};
        //System.out.println(Arrays.toString(fib(3)));
        System.out.println(fibonacciSearch(arr, 1234));
    }

    /**
     * 生成一个大小为n的斐波那契数列
     * @param n fibonacci数组元素个数
     * @return 返回int[]
     */
    public static int[] fib(int n){
        if (n <= 2){
            return null;
        }
        int[] f = new int[n];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < n; i++) {
            f[i] = f[i-1] + f[i-2];
        }
        return f;
    }

    /**
     * 斐波那契查找算法
     * @param arr 数组
     * @param findVal 要查找的值
     * @return 返回索要查找值的索引
     */
    public static int fibonacciSearch(int[] arr, int findVal){

        int low = 0;
        int high = arr.length-1;
        int k = 0;
        int mid = 0;
        int[] f = fib(20);
        while(high > (f[k]-1)){
            k++;
        }
        //因为f[k]的值可能大于arr的长度，因此需要使用Arrays类，构造一个新的数组，并指向arr[]
        int[] temp = Arrays.copyOf(arr, f[k]);
        for (int i = high+1; i < temp.length; i++) {
            temp[i] = arr[high];//多余的位数全部填充最后为arr[high]
        }

        while (low <= high){
            mid = low + f[k-1]-1;
            if (findVal < temp[mid]){
                high = mid - 1;
                k--;
            }else if (findVal > temp[mid]){
                low = mid + 1;
                k -= 2;
            }else {
                //需要确定返回的是哪个
                if (mid <= high){
                    return mid;
                }
                return high;
            }
        }
        return -1;
    }
}
